// 字符串
// "消消乐" 问题，要想到使用栈的思想解决

// 例题 2：
// 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
//
//        注意：如果对空文本输入退格字符，文本继续为空。
//
//        示例 1：
//
//        输入：s = "ab#c", t = "ad#c"
//        输出：true
//        解释：s 和 t 都会变成 "ac"。
//        示例 2：
//
//        输入：s = "ab##", t = "c#d#"
//        输出：true
//        解释：s 和 t 都会变成 ""。
//        示例 3：
//
//        输入：s = "a#c", t = "b"
//        输出：false
//        解释：s 会变成 "c"，但 t 仍然是 "b"。
//
//
//        提示：
//
//        1 <= s.length, t.length <= 200
//        s 和 t 只含有小写字母以及字符 '#'
//
//
//        进阶：
//
//        你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

// 解题思路：
// 和例题 1 一摸一样
// 相邻的字符消除 - 是典型的“消消乐”问题，可以使用栈的思想解决
// 字符不同，执行进栈操作，字符相同，执行出栈操作

public class BackspaceCompare {
    public boolean backspaceCompare(String s, String t) {
        int n1 = s.length();
        int n2 = t.length();
        StringBuilder ss = new StringBuilder();
        char[] sArr = s.toCharArray();
        int pos1 = 0;
        for(int i = 0; i < n1; i++){
            if(sArr[i] == '#'){
                if(pos1 > 0){
                    ss.deleteCharAt(pos1 - 1);
                    pos1--;
                }
            }else{
                ss.append(sArr[i]);
                pos1++;
            }
        }
        StringBuilder tt = new StringBuilder();
        char[] tArr = t.toCharArray();
        int pos2 = 0;
        for(int j = 0; j < n2; j++){
            if(tArr[j] == '#'){
                if(pos2 > 0){
                    tt.deleteCharAt(pos2 - 1);
                    pos2--;
                }
            }else{
                tt.append(tArr[j]);
                pos2++;
            }
        }
        return ss.toString().equals(tt.toString());
    }
}
